package slidingWindow;

//https://leetcode.cn/problems/minimum-window-substring/description/
public class l_76 {
    public String minWindow(String s, String t) {
        int n = s.length(), m = t.length(), kinds = 0, begin = -1, len = Integer.MAX_VALUE;
        int[] hash1 = new int[128], hash2 = new int[128];
        byte[] ss = s.getBytes(), tt = t.getBytes();
        for(byte ch: tt) if(hash2[ch]++ == 0) kinds++; //记录目标字符串的字符种类
        //count记录的是满足滑动窗口内有效字符数量的种类, 不是数量
        //维护滑动窗口内有效字符种类, 满足就左指针右移直到不满足, 左指针右移一次就记录一次答案!
        for(int left = 0, right = 0, count = 0; right < n; right++)
        {
            int in = ss[right];
            if(++hash1[in] == hash2[in]) count++;
            while(count == kinds) //满足就一直右移左指针
            {
                int out = ss[left];
                if(right - left + 1 <= len) //记录答案
                {
                    begin = left;
                    len = right - left + 1;

                }
                if(hash1[out]-- == hash2[out]) count--;
                left++;
            }
        }
        return begin == -1 ? "" : s.substring(begin, begin + len);
    }
}
